import com.sun.org.apache.xerces.internal.impl.io.UCSReader;
import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

import javax.print.DocFlavor;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 28463
 * Date: 2022—07—16
 * Time: 16:52
 */
public class Sort {
    /**
     * @param array:
     * 时间复杂度：
     *       最坏：O(n^2) 数据元素全部逆序时
     *       最好：O(n) 数据元素全部有序时
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @description 直接插入排序
     * 数据元素基本上有序时，使用效果最好
     */
    public void insertSort(int[] array) {
        for (int i  = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static void shell(int[] array,int gap) {
        for (int i  = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    /**
     * @param array:
     * 时间复杂度：O(n^1.3 - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @description 希尔排序
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
/*        int[] drr = {5,2,1};
        for (int i = 0; i < drr.length; i++) {
            shell(array,drr[i]);
        }*/
    }
    /**
     * 数据复杂度：O(n^2) （对数据不敏感，不管数据有序还是无序都是这样）
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @description 直接选择排序
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //每次将i下标的值当做最小值
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                   minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    private static void swap(int[] array,int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 直接选择排序的改进版
     * @return void
     * @description 两个变量找最大最小值交换
     */
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length-1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,maxIndex);
            //修正maxIndex下标
            if(left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    /**
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @description 堆排序
     */
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length-1;
        while(end >= 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent= (array.length-1-1)/2; parent >= 0 ; parent--) {
           shiftDown(array,parent,array.length);
        }
    }
    //向下调整
    private static void  shiftDown(int[] array,int parent,int len) {
        int child = 2*parent+1;
        while(child < len) {
            if(child+1 < len && array[child] < array[child+1]){
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    /**
     * 时间复杂度：O(n^2)
     * 优化后的代码，时间复杂度：0（n）
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @description 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg ) {
                break;
            }//这一趟没有发生交换，说明有序
        }
    }

    /**
     * 时间复杂度：
     * 最优：O(n*logn)  每次均分待排序数组
     * 最坏：O(n^2)  数组有序或逆序
     * 空间复杂度：最好：O(logN)
     *          最坏：O(N)   当n足够大时，递归的深度就大
     * 稳定性：不稳定
     * @description Hearo法 找基准
     */
    public static void quickSortHearo(int[] array) {
        quick2(array,0, array.length-1);
    }


    private static void quick(int[] array,int left, int right) {
        //取= 是只有一个节点了 >有可能没有子树
        if (left >= right) {
            return;
        }
        int pivot = partition3(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }


    //找k Hearo法 找基准
    private static int partition1(int[] array,int start, int end) {
        int i = start;
        int key = array[start];
        //取等号，防止死循环
        while (start < end) {
            while (start < end && array[end] >= key) {
                end--;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }

    //挖坑法 拿出k，添补空白位置
    private static int partition2(int[] array,int start, int end) {
        int key = array[start];

        while(start < end) {
            while(start < end && array[end] >= key) {
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }

    //前后指针法
    private static int partition3(int[] array,int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[left]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left); return prev;
    }
    /**
     *为了解决栈溢出问题
     * @description 三数取中法
     */
    private static int midNumIndex(int[] array, int left, int right) {
        int mid = (left+right) / 2;

        if (array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }
    //三数取中法的递归实现
    private static void quick1(int[] array,int left, int right) {
        //取= 是只有一个节点了 >有可能没有子树
        if (left >= right) {
            return;
        }
        int index = midNumIndex(array,left,right);
        //找到三数中，中间大小的数字，和第一个交换
        swap(array,left,right);
        //此时就按之前正常那个Hearo法执行就可以了
        int pivot = partition1(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    /**
     * 继续改进
     * 三数取中，方便找基准
     * 小区间最后一层 直接插入排序，优化递归深度
     * @description
     */
    private static void quick2(int[] array,int left, int right) {
        if(left >= right) {
            return;
        }
        //小区间 直接插入排序，优化递归深度
        if(right - left + 1 <= 15) {
            //趋于有序，用直接插入排序
            insertSort2(array,left,right);
            return;
        }
        //三数取中
        int index = midNumIndex(array,left,right);
        //找到三数中，中间大小的数字，和第一个交换
        swap(array,left,right);
        //此时就按之前正常那个Hearo法执行就可以了
        int pivot = partition1(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    //快排改进后使用的改进插排（给指定的区间进行排序）
    private static void insertSort2(int[] array,int start, int end) {
        for (int i  = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    /**
     *
     *
     * @description 非递归实现快排
     */
    public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot = partition2(array,left,right);

        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition1(array, left, right);
            //当左边或右边区间只剩一个元素时，不用给栈中放
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    /**
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     * @description 归并排序
     */
    public static  void mergerSort1(int[] array) {
        mergerSortFunc(array,0, array.length-1);
    }
    //分割
    private static void mergerSortFunc(int[] array,int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left+right)/2;
        //1.分解左边
        mergerSortFunc(array,left,mid);
        //2.分解右边
        mergerSortFunc(array,mid+1,right);
        //3.进行合并
        merge(array,left,right,mid);
    }
    //合并
    private static void merge(int[] array,int start, int end, int midIndex) {
        //合并放到一个新数组
        int[] tmpArr = new int[end-start+1];
        int k = 0;//tmpArrA数组下标

        int s1 = start;
        int s2 = midIndex+1;

        //两个归并段，都有数据
        while(s1 <= midIndex && s2 <= end) {
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        //此时，说明有个归并段中没有了数据，拷贝到另一半的全部到tmpArr数组中
        while(s1 <= midIndex) {
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= end) {
            tmpArr[k++] = array[s2++];
        }
        //把排好序的数字 拷贝回 原来的数字
        for (int i = 0; i < k; i++) {
            array[i+start] = tmpArr[i];
        }
    }

    public static  void mergerSort2(int[] array) {
        int gap = 1;//每组的数据
        while(gap < array.length) {
            for (int i = 0; i < array.length; i += gap*2) {
                int s1 = i;
                int e1 = s1+gap-1;
                if(e1 >= array.length) {
                    e1 = array.length-1;
                }
                int s2 = e1+1;
                if(s2 >= array.length) {
                    s2 = array.length -1;
                }
                int e2 = s2+gap-1;
                if (e2 >= array.length) {
                    e2 = array.length-1;
                }
                merge(array,s1,e2,e1);
            }
            gap *= 2;
        }
    }

    /**
     * 时间复杂度：O(n+范围)
     * 空间复杂度：O(范围)
     * 稳定性：稳定
     * 适合给定范围的数据 进行排序
     * @description 计数排序
     */
    public static void countSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if (array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //确定了最大 最小值
        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        //开始遍历array数组 进行计数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            count[val-minVal]++;
        }
        int index = 0;//array数组下标
        for (int i = 0; i < count.length; i++) {
            //确保当前count数组 可以检查完
            while(count[i] != 0) {
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

}
